{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sorting Three Groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将三个组排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;。<br />\n",
    "<br />\n",
    "从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;的数字被分为编号从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>3</code>&nbsp;的三个组，数字&nbsp;<code>i</code>&nbsp;属于组&nbsp;<code>nums[i]</code>&nbsp;。注意，有的组可能是&nbsp;<strong>空的</strong>&nbsp;。<br />\n",
    "<br />\n",
    "你可以执行以下操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择数字&nbsp;<code>x</code>&nbsp;并改变它的组。更正式的，你可以将&nbsp;<code>nums[x]</code>&nbsp;改为数字&nbsp;<code>1</code>&nbsp;到&nbsp;<code>3</code>&nbsp;中的任意一个。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你将按照以下过程构建一个新的数组&nbsp;<code>res</code>&nbsp;：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>将每个组中的数字分别排序。</li>\n",
    "\t<li>将组&nbsp;<code>1</code>&nbsp;，<code>2</code>&nbsp;和&nbsp;<code>3</code>&nbsp;中的元素&nbsp;<strong>依次</strong>&nbsp;连接以得到&nbsp;<code>res</code>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>如果得到的&nbsp;<code>res</code>&nbsp;是 <strong>非递减</strong>顺序的，那么我们称数组&nbsp;<code>nums</code>&nbsp;是 <strong>美丽数组</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回将<em>&nbsp;</em><code>nums</code>&nbsp;变为&nbsp;<strong>美丽数组</strong>&nbsp;需要的最少步数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,3,2,1]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>以下三步操作是最优方案：\n",
    "1. 将 nums[0] 变为 1 。\n",
    "2. 将 nums[2] 变为 1 。\n",
    "3. 将 nums[3] 变为 1 。\n",
    "执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3,4] ，组 2 和组 3 都为空。所以 res 等于 [0,1,2,3,4] ，它是非递减顺序的。\n",
    "三步操作是最少需要的步数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,3,2,1,3,3]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>以下两步操作是最优方案：\n",
    "1. 将 nums[1] 变为 1 。\n",
    "2. 将 nums[2] 变为 1 。\n",
    "执行以上操作后，将每组中的数字排序，组 1 为 [0,1,2,3] ，组 2 为空，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。\n",
    "两步操作是最少需要的步数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,2,2,2,3,3]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不需要执行任何操作。\n",
    "组 1 为空，组 2 为 [0,1,2,3] ，组 3 为 [4,5] 。所以 res 等于 [0,1,2,3,4,5] ，它是非递减顺序的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 3</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sorting-three-groups](https://leetcode.cn/problems/sorting-three-groups/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sorting-three-groups](https://leetcode.cn/problems/sorting-three-groups/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3,2,1]', '[1,3,2,1,3,3]', '[2,2,2,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import Deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        d: Deque[int] = deque(nums)\n",
    "        nOps: int = 0\n",
    "            \n",
    "        while len(d) > 1:\n",
    "            if d[0] == d[-1]:\n",
    "                d.popleft()\n",
    "                d.pop()\n",
    "            elif d[0] < d[-1]:\n",
    "                d.appendleft(d.popleft() + d.popleft())\n",
    "                nOps += 1\n",
    "            else:\n",
    "                d.append(d.pop() + d.pop())\n",
    "                nOps += 1\n",
    "\n",
    "        return nOps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i, j = 0, n-1\n",
    "        left, right = nums[i], nums[j]\n",
    "        res = 0\n",
    "        while i < j:\n",
    "            if left < right:\n",
    "                i += 1\n",
    "                left += nums[i]\n",
    "                res += 1\n",
    "            elif left > right:\n",
    "                j -= 1\n",
    "                right += nums[j]\n",
    "                res += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                left, right = nums[i], nums[j]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre = nums[i]\n",
    "        suf = nums[j]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1 \n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        ans = 0\r\n",
    "        i, j = 0, n - 1\r\n",
    "        pre, suf = nums[0], nums[-1]\r\n",
    "        while i < j:\r\n",
    "            if pre < suf:\r\n",
    "                i += 1\r\n",
    "                pre += nums[i]\r\n",
    "                ans += 1\r\n",
    "            elif pre > suf:\r\n",
    "                j -= 1\r\n",
    "                suf += nums[j]\r\n",
    "                ans += 1\r\n",
    "            else:\r\n",
    "                i += 1\r\n",
    "                j -= 1\r\n",
    "                pre = nums[i]\r\n",
    "                suf = nums[j]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans\n",
    "    \"\"\"\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        cnt = -2\n",
    "        left, right = 0, len(nums)-1\n",
    "        res = len(nums)-1 if left < right else 0\n",
    "        ls, rs = 0, 0\n",
    "        while left <= right:\n",
    "            if ls <= rs:\n",
    "                ls += nums[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                rs += nums[right]\n",
    "                right -= 1\n",
    "            cnt += 1\n",
    "            if ls == rs:\n",
    "                res = min(res, cnt + self.minimumOperations(nums[left:(1+right)]))\n",
    "        return res\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r =0, n - 1\n",
    "        left, right = nums[l], nums[r]\n",
    "\n",
    "        if n == 1 : return 0\n",
    "\n",
    "        res = 0\n",
    "        while l < r:\n",
    "\n",
    "            if left < right:\n",
    "                l += 1\n",
    "                left += nums[l]\n",
    "                res += 1\n",
    "            \n",
    "            elif left > right:  \n",
    "                r -= 1\n",
    "                right += nums[r]\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "                left, right = nums[l], nums[r]\n",
    "\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        i = 0 \n",
    "        j = len(nums) - 1\n",
    "        res = 0\n",
    "        while i < j:\n",
    "            left = nums[i]\n",
    "            right = nums[j]\n",
    "            while left != right and i < j:\n",
    "                if left > right:\n",
    "                    j -= 1\n",
    "                    right += nums[j]\n",
    "                    res += 1\n",
    "                elif left < right:\n",
    "                    i += 1\n",
    "                    left += nums[i]\n",
    "                    res += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return res if j >= 0 else len(nums) -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums = deque(nums)\n",
    "\n",
    "        ans = 0\n",
    "        while len(nums) > 1:\n",
    "            while len(nums) > 1 and nums[0] != nums[-1]:\n",
    "                if nums[0] > nums[-1]:\n",
    "                    nums.append(nums.pop() + nums.pop())\n",
    "                else:\n",
    "                    nums.appendleft(nums.popleft() + nums.popleft())\n",
    "                ans += 1\n",
    "            \n",
    "            nums.popleft()\n",
    "            if nums:\n",
    "                nums.pop()\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lf, ri = 0, n - 1\n",
    "        res = 0\n",
    "        while lf < ri:\n",
    "            if nums[lf] == nums[ri]:\n",
    "                lf += 1\n",
    "                ri -= 1\n",
    "                continue\n",
    "\n",
    "            else:\n",
    "                if nums[lf] > nums[ri]:\n",
    "                    nums[ri - 1] += nums[ri]\n",
    "                    ri -= 1\n",
    "                else:\n",
    "                    nums[lf + 1] += nums[lf]\n",
    "                    lf += 1\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        left, right=0,len(nums)-1\n",
    "        ans = 0\n",
    "        while left<right:\n",
    "            if nums[left] == nums[right]:\n",
    "                left+=1 \n",
    "                right-=1\n",
    "            elif nums[left]<nums[right]:\n",
    "                nums[left+1]+=nums[left]\n",
    "                ans+=1\n",
    "                left+=1\n",
    "            else:\n",
    "                nums[right-1]+=nums[right]\n",
    "                ans+=1\n",
    "                right-=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, prev):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if nums[i] < prev:\n",
    "                return 1 + dp(i+1, prev)\n",
    "            elif prev == 3:\n",
    "                return dp(i+1, prev)\n",
    "            else:\n",
    "                return min(dp(i+1, nums[i]), int(prev < nums[i])+dp(i+1, prev))\n",
    "\n",
    "        return dp(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        list_maxlen = [4]\n",
    "        for i in range(len(nums)):\n",
    "            j = 0\n",
    "            flag_in = 0\n",
    "            while j < len(list_maxlen):\n",
    "                if nums[i] < list_maxlen[j]:\n",
    "                    list_maxlen[j] = nums[i]\n",
    "                    flag_in = 1\n",
    "                    break\n",
    "                j += 1\n",
    "            if flag_in == 0:\n",
    "                list_maxlen.append(nums[i])\n",
    "            print(list_maxlen)\n",
    "        return len(nums) - len(list_maxlen)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        result = [1, 1, 1]\n",
    "        index = 0\n",
    "        result[nums[index] - 1] -= 1\n",
    "\n",
    "        index = 1\n",
    "        while index < len(nums):\n",
    "            num = nums[index]\n",
    "            new_result = []\n",
    "            new_result.append(result[0] + (0 if num == 1 else 1))\n",
    "            new_result.append(min(result[1], result[0]) + (0 if num == 2 else 1))\n",
    "            new_result.append(min(result[2], result[1], result[0]) +  (0 if num == 3 else 1))\n",
    "            result = new_result\n",
    "            index += 1\n",
    "\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        dp = [0]*4\n",
    "        for x in nums:\n",
    "            dp[x] += 1\n",
    "            dp[2] = max(dp[1],dp[2])\n",
    "            dp[3] = max(dp[3],dp[2])\n",
    "        return len(nums) - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        list_maxlen = [4]\n",
    "        for i in range(len(nums)):\n",
    "            print(list_maxlen)\n",
    "            j = 0\n",
    "            flag_in = 0\n",
    "            while j < len(list_maxlen):\n",
    "                if nums[i] < list_maxlen[j]:\n",
    "                    list_maxlen[j] = nums[i]\n",
    "                    flag_in = 1\n",
    "                    break\n",
    "                j += 1\n",
    "            if flag_in == 0:\n",
    "                list_maxlen.append(nums[i])\n",
    "            print(list_maxlen)\n",
    "        return len(nums) - len(list_maxlen)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def g(i):\n",
    "           res =1\n",
    "           for j in range(i+1,n):\n",
    "               if nums[i]<=nums[j]:\n",
    "                  res=max(res,g(j)+1)\n",
    "           return res\n",
    "        c=0   \n",
    "        for i in range(n):         \n",
    "           c=max(c,g(i))\n",
    "        return n-c        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        # 这里要求max(1)<min(2),最后一位变或不变\n",
    "        @cache\n",
    "        def dfs(i:int,val:int)->int:\n",
    "            if i <0:\n",
    "                return 0\n",
    "            res=inf\n",
    "            for j in range(val,0,-1):\n",
    "                res=min(dfs(i-1,j)+int(j!=nums[i]),res)\n",
    "            return res        \n",
    "        return dfs(n-1,3)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
